package likou.dtgh.beibao;

import java.util.Arrays;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/10 10:57
 */
public class _879 {
    public static void main(String[] args) {
        System.out.println(profitableSchemes(5,3,new int[]{2,2},new int[]{2,3}));
    }

    static int mod = (int)1e9+7;
    public static int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;
        int[][] f = new int[n + 1][min + 1];//f[j][k]：j个工人，最少需要盈利k的方案数。
        for (int i = 0; i <= n; i++) f[i][0] = 1;
        //遍历每一个任务
        for (int i = 1; i <= m; i++) {
            //当前任务：a是需要工人数，b是盈利
            int a = gs[i - 1], b = ps[i - 1];
            for (int j = n; j >= a; j--) {
                for (int k = min; k >= 0; k--) {
                    //当前还差的盈利数
                    int u = Math.max(k - b, 0);
                    //
                    f[j][k] += f[j - a][u];
                    //维护 int
                    if (f[j][k] >= mod) f[j][k] -= mod;
                }
            }
            for (int j=0;j<n;j++){
                System.out.println(Arrays.toString(f[j]));
            }
            System.out.println();
        }
        return f[n][min];
    }
}
